\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\textbf{使用主席树在线做，我们不能使用权值线段树建主席树}

\begin{itemize}
\item
  与之前主席树的权值线段树思路不同，此题的思路是建立 \(n\) 颗线段树，第
  \(i\) 颗线段树存储区间 \([1,i]\) 的信息
\item
  其中每个节点维护 \(sum\)
  ,表示节点对应区间中数的个数，因此每棵线段树中只保留每个数最后出现的位置
\item
  举个例子，序列为 \(5,5,5,5,5\)，则第 \(1\) 颗线段树中只有第一个位置
  \(sum\) 为 \(1\)，然后第二颗线段树从第一颗线段树继承过来，由于 \(5\)
  这个数字之前出现过，因此在第二颗线段树中令第一个位置的 \(sum\) 为
  \(0\)，令第二个位置的 \(sum\) 为 \(1\)，来保存每个数字最后出现的位置
\item
  因此查询区间 \([ l , r ]\) 时，就在第 \(r\) 颗线段树中查询区间
  \([ l ,n]\) 中数的个数即可
\end{itemize}

\begin{lstlisting}
const int N = 1e6 + 10;
struct Chairman_Tree{
	int l , r , sum;
} tree[N * 40];
vector<int>vec;
int root[N] , a[N] , Ctot , last[N]; //last[i]表示上一次出现 i 的位置
int n , m;
void update(int l , int r , int pre , int &now , int pos , int val)
{
	tree[++ Ctot] = tree[pre];
	tree[Ctot].sum += val;
	now = Ctot;
	if(l == r) return ;
	int mid = l + r >> 1;
	if(pos <= mid) update(l , mid , tree[pre].l , tree[now].l , pos , val);
	else update(mid + 1 , r , tree[pre].r , tree[now].r , pos , val);
}
int query(int l , int r , int L , int id)
{
	if(L <= l) return tree[id].sum;
	int mid = l + r >> 1;
	if(L <= mid) return query(l , mid , L , tree[id].l) + tree[tree[id].r].sum;
	return query(mid + 1 , r , L , tree[id].r);
}
int get_id(int x){
	return lower_bound(vec.begin() , vec.end() , x) - vec.begin() + 1;
}
signed main()
{
	read(n);
	rep(i , 1 , n)
	{
		read(a[i]);
		vec.push_back(a[i]);
	}
	sort(vec.begin() , vec.end());
	vec.erase(unique(vec.begin() , vec.end()) , vec.end()) ;
	rep(i , 1 , n)
	{
		if(last[a[i]])
		{
			int help = 0;
			update(1 , n , root[i - 1] , help , last[a[i]] , -1);
			/*
			先用 help 来转移 root[i - 1] , 在把 help 树上的 last[a[i]] --
			再把 help 转移给 root[i] , 同时让 root[i] 树上的 i ++
			*/
			update(1 , n , help , root[i] , i , 1);
		}
		else update(1 , n , root[i - 1] , root[i] , i , 1);
		last[a[i]] = i;
	}
	read(m);
	while(m --)
	{
		int l , r;
		read(l) , read(r);
		cout << query(1 , n , l , root[r]) << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
